package com.atguigu.distributed.lock.leecode.midsearch;

/**
 * 二维数组中查找
 * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * [
 * [1,2,8,9],
 * [2,4,9,12],
 * [4,7,10,13],
 * [6,8,11,15]
 * ]
 * 给定 target = 7，返回 true。
 * <p>
 * 给定 target = 3，返回 false。
 */
public class ArraysFind {
    public boolean Find(int target, int[][] array) {
        //优先判断特殊
        if (array.length == 0) {
            return false;
        }
        int n = array.length;
        if (array[0].length == 0) {
            return false;
        }
        int m = array[0].length;
        //从最左下角的元素开始往右或往上
        for (int i = n - 1, j = 0; i >= 0 && j < m; ) {
            if (array[i][j] > target) {
                i--;
            } else if (array[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }

    public boolean find2(int target, int[][] array) {
        //优先判断特殊
        if (array.length == 0) {
            return false;
        }
        int n = array.length;
        if (array[0].length == 0) {
            return false;
        }
        int m = array[0].length;
        //从最左下角的元素开始往右或往上查找元素
        for (int i = n - 1, j = 0; i >= 0 && j < m; ) {
            if(array[i][j]>target){
                i--;
            }else if(array[i][j]<target){
                j++;
            }else {
                return true;
            }

        }
        return false;
    }
}
